//现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。 
//
// 
//
// 示例 1： 
//
// 
//输入: bamboo_len = 12
//输出: 81
// 
//
//提示：
//
// 
// 2 <= bamboo_len <= 58 
// 
//
// 注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/ 
//
// Related Topics 数学 动态规划 👍 619 👎 0


package leetcode.editor.cn;

// [LCR 131]砍竹子 I

public class JianShengZiLcof_LCR131 {
    public static void main(String[] args) {
        Solution solution = new JianShengZiLcof_LCR131().new Solution();
        solution.cuttingBamboo(12);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int cuttingBamboo(int bamboo_len) {
            //dp[i]将i长度的竹子分成至少两份后的最大乘积
            int[] dp = new int[bamboo_len + 1];
            for (int i = 2; i <= bamboo_len; i++) {
                for (int j = 1; j < i; j++) {
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                }
            }
            return dp[bamboo_len];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}